package org.neptune.common.sort;

/** 归并排序 */
public class MergeSort {

	/**
	 * 归并排序（Merge
	 * Sort）与快速排序思想类似：将待排序数据分成两部分，继续将两个子部分进行递归的归并排序；然后将已经有序的两个子部分进行合并，最终完成排序。
	 * 其时间复杂度与快速排序均为O(nlogn)，但是归并排序除了递归调用间接使用了辅助空间栈，还需要额外的O(n)空间进行临时存储。从此角度归并排序略逊于快速排序，但是归并排序是一种稳定的排序算法，快速排序则不然。
	 * 所谓稳定排序，表示对于具有相同值的多个元素，其间的先后顺序保持不变。对于基本数据类型而言，一个排序算法是否稳定，影响很小，但是对于结构体数组，稳定排序就十分重要。例如对于student结构体按照关键字score进行非降序排序：
	 */
	public static void main(String[] args) {
		int[] list = { 50, 10, 90, 30, 70 };
		System.out.println("************归并排序************");
		System.out.println("排序前：");
		display(list);
		System.out.println("排序后：");
		mergeSort(list, new int[list.length], 0, list.length - 1);
		display(list);
	}

	/**
	 * 归并排序算法
	 *
	 * @param list
	 *            待排序的列表
	 * @param tempList
	 *            临时列表
	 * @param head
	 *            列表开始位置
	 * @param rear
	 *            列表结束位置
	 */
	public static void mergeSort(int[] list, int[] tempList, int head, int rear) {
		if (head < rear){
			// 取分割位置
			int middle = (head + rear) / 2;
			// 递归划分列表的左序列
			mergeSort(list, tempList, head, middle);
			// 递归划分列表的右序列
			mergeSort(list, tempList, middle + 1, rear);
			// 列表的合并操作
			merge(list, tempList, head, middle + 1, rear);
		}
	}

	/**
	 * 合并操作(列表的两两合并)
	 *
	 * @param list
	 * @param tempList
	 * @param head
	 * @param middle
	 * @param rear
	 */
	public static void merge(int[] list, int[] tempList, int head, int middle, int rear) {
		// 左指针尾
		int headEnd = middle - 1;
		// 右指针头
		int rearStart = middle;
		// 临时列表的下标
		int tempIndex = head;
		// 列表合并后的长度
		int tempLength = rear - head + 1;

		// 先循环两个区间段都没有结束的情况
		while ((headEnd >= head) && (rearStart <= rear)){
			// 如果发现右序列大，则将此数放入临时列表
			if (list[head] < list[rearStart]){
				tempList[tempIndex++] = list[head++];
			} else{
				tempList[tempIndex++] = list[rearStart++];
			}
		}

		// 判断左序列是否结束
		while (head <= headEnd){
			tempList[tempIndex++] = list[head++];
		}

		// 判断右序列是否结束
		while (rearStart <= rear){
			tempList[tempIndex++] = list[rearStart++];
		}

		// 交换数据
		for (int i = 0; i < tempLength; i++){
			list[rear] = tempList[rear];
			rear--;
		}
	}

	/** 遍历打印 */
	public static void display(int[] list) {
		if (list != null && list.length > 0){
			for (int num : list){
				System.out.print(num + " ");
			}
			System.out.println("");
		}
	}

	// public static void main(String[] args) {
	// // TODO Auto-generated method stub
	// int[] arr= {3,8,6,2,1,8};
	// mergeSort(arr,0,arr.length-1);
	// System.out.println(Arrays.toString(arr));
	// }
	/**
	 * 递归拆分
	 * 
	 * @param arr
	 *            待拆分数组
	 * @param left
	 *            待拆分数组最小下标
	 * @param right
	 *            待拆分数组最大下标
	 */
	public static void mergeSort(int[] arr, int left, int right) {
		int mid = (left + right) / 2; // 中间下标
		if (left < right){
			mergeSort(arr, left, mid);// 递归拆分左边
			mergeSort(arr, mid + 1, right);// 递归拆分右边
			sort(arr, left, mid, right);// 合并左右
		}
	}

	/**
	 * 合并两个有序子序列
	 * 
	 * @param arr
	 *            待合并数组
	 * @param left
	 *            待合并数组最小下标
	 * @param mid
	 *            待合并数组中间下标
	 * @param right
	 *            待合并数组最大下标
	 */
	public static void sort(int[] arr, int left, int mid, int right) {
		int[] temp = new int[right - left + 1]; // 临时数组，用来保存每次合并年之后的结果
		int i = left;
		int j = mid + 1;
		int k = 0;// 临时数组的初始下标
		// 这个while循环能够初步筛选出待合并的了两个子序列中的较小数
		while (i <= mid && j <= right){
			if (arr[i] <= arr[j]){
				temp[k++] = arr[i++];
			} else{
				temp[k++] = arr[j++];
			}
		}
		// 将左边序列中剩余的数放入临时数组
		while (i <= mid){
			temp[k++] = arr[i++];
		}
		// 将右边序列中剩余的数放入临时数组
		while (j <= right){
			temp[k++] = arr[j++];
		}
		// 将临时数组中的元素位置对应到真真实的数组中
		for (int m = 0; m < temp.length; m++){
			arr[m + left] = temp[m];
		}
	}

}
